package leetcode.code2179;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public long goodTriplets(int[] nums1, int[] nums2) {
		int n = nums2.length;
		int[] hash = new int[n];// nums2中num的索引
		for (int i = 0; i < n; i++) {
			hash[nums2[i]] = i;// value的下标
		}
		int[] pos2 = new int[n];// num1在nums2中顺序数组,pos2[i]=k,i是nums1的index，k是nums2的index
		for (int i = 0; i < n; i++) {
			pos2[i] = hash[nums1[i]];// nums1中value在nums2中下标
		}
		// pos2中满足三元升序的个数，就是nums1在nums2中满足三元升序的个数
		long[] left = new long[n];// pos2[i]==k, left[k]在pos2中左边有几个value比k小的数，用int挂在147用例
		long[] right = new long[n];// pos2[i]==k, right[k]在pos2中右边有几个value比k大的数
		this.find(pos2, 0, n - 1, left, right);
		long ans = 0;
		for (int i = 0; i < n; i++) {
			ans += left[i] * right[i];
		}
		return ans;
	}

	private void find(int[] pos2, int L, int R, long[] left, long[] right) {
		if (L == R) {
			return;
		}
		int mid = ((R - L) >> 1) + L;
		this.find(pos2, L, mid, left, right);
		this.find(pos2, mid + 1, R, left, right);
		this.merge(pos2, L, mid, R, left, right);
	}

	private void merge(int[] pos2, int L, int mid, int R, long[] left, long[] right) {
		int l1 = L, l2 = mid + 1;
		int r1 = mid, r2 = R;
		int size = R - L + 1;
		int[] temp = new int[size];
		int p = 0;
		while (l1 <= r1 && l2 <= r2) {
			int num1 = pos2[l1], num2 = pos2[l2];
			if (num1 < num2) {
				right[num1] += R - l2 + 1;// num1右边有这么些个比他大的。
				temp[p++] = num1;
				l1++;
			} else {
				left[num2] += l1 - L;
				temp[p++] = num2;
				l2++;
			}
		}
		while (l1 <= r1) {
			int num1 = pos2[l1++];
			temp[p++] = num1;
		}
		while (l2 <= r2) {
			int num2 = pos2[l2++];
			temp[p++] = num2;
			left[num2] += mid - L + 1; // l1-r1范围所有的数都比剩下的小
		}
		p = L;
		for (int i = 0; i < size; i++) {
			pos2[p++] = temp[i];
		}
	}

	@Override
	public void debug4() {
		HelpDebug.compare(4, this.goodTriplets(HelpDebug.str2array3("[4,0,1,3,2]"), HelpDebug.str2array3("[4,1,0,2,3]")));
		HelpDebug.compare(1, this.goodTriplets(HelpDebug.str2array3("[2,0,1,3]"), HelpDebug.str2array3("[0,1,2,3]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
